<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1161：[CTSC2004]数字搜索regular</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[CTSC2004]数字搜索regular</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[CTSC2004]数字搜索regular</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [CTSC2004]数字搜索regular                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：162MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>HURRICANE小组最近接到了一个搜索文本的任务，即从一个由数字构成的长文本中，匹配满足指定条件的子串。搜索的条件采用形如&lsquo;(0+10*1)*10*&rsquo;这样的正则表达式来描述。其中正则表达式的归纳定义如下： 1. 0, 1, &hellip;, 9，0*, 1*, &hellip;, 9*是正则表达式； 2. 如果A和B是正则表达式，则(A)，A+B，AB，(A)*都是正则表达式； 3. 只有按以上方法构造出来的表达式才是正则表达式。 其中，A+B表示&ldquo;或者&rdquo;关系，AB表示&ldquo;连接&rdquo;关系，(A)*表示A的内容&ldquo;重复&rdquo;零次或者多次。比如正则表达式(12+3)(4+5)6*，就可以匹配以124，125，34，35之一开头，之后接零0个或任意多个6的字符串（例如字符串12566）。正则表达式(1+0)*可以匹配所有由0和1构成的字符串，或者是空串。如果一个正则表达式不能匹配空串，则称它是非空的。本题考虑的都是非空正则表达式。如果在给定文本的某一个位置，存在一个以该位置结束的子串，能够被给定的非空正则表达式匹配，则称该位置是可匹配的。现在HURRICANE小组接到的任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么？【任务描述】你的程序需要根据给定的输入，给出符合题意的输出：  输入包括一个满足如上定义的正则表达式，以及一长串文本； 你需要根据输入的正则表达式及文本，找出文本中所有可匹配的位置； 你给出的输出需要包括所有可匹配的位置。</p></p><hr/><h3>输入格式</h3><p><p>第一行描述一个正则表达式，第二行为需要处理的文本：第一行的正则表达式包括由一个空格分开的两个部分：一个非负整数n（1&le; n&le; 10），表示我们所要考虑的数字集（即在正则表达式和文本中所出现的数字）是0, 1, &hellip;, n&ndash;1。接下来是一个正则表达式，它由{&lsquo;(&lsquo;, &rsquo;)&rsquo;, &rsquo;+&rsquo;, &rsquo;*&rsquo;}中的4个符号和{0, &hellip;, n&ndash;1}中的数字构成，表达式的长度不超过500个字符。第二行为一个由0到n-1之间数字构成的字符串，为需要处理的文本。该文本长度不超过10,000,000个字符。</p></p><hr/><h3>输出格式</h3><p><p>输出只有一行，包括一些由空格分开的整数，按从小到大的顺序依次输出所需处理的文本中每一个可匹配的位置。</p></p><hr/><h3>样例输入</h3><pre>4 12333+33
312331
说明：对于输入示例，需要处理的文本是’312331’，其中只有第5个字符所在的位置（下划线所在处）是可匹配的。这时正则表达式’12333+33'中的’33’可以与之匹配。

</pre><hr/><h3>样例输出</h3><pre>5</pre><hr/><h3>提示</h3><p><p>【评分方法】<br />
本题目一共有十个测试点，每个测试点的分数为总分数的10%。对于每个测试点来说，如果你给出的答案正确，那么你将得到该测试点全部的分数，否则得0分。<br />
提示：在本次的测试数据中，有6个测试点中的正则表达式不出现&rsquo;*&rsquo;，其中有3个测试点，正则表达式只由数字和&rsquo;+&rsquo;构成。有一个测试点的待处理文本不超过1,000,000个字符。该题有严格的时间限制，请尽量优化你的算法。</p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1161" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1161" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>